/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package RedBlackTree;

/**
 *
 * @author Nathan
 */
public class RedBlackTree {

  private TNode<Integer> root;
  private int height;

  public static void main(String[] args) {
    RedBlackTree RB_Tree = new RedBlackTree();    

    /*
     * This loop will run the program with sorted arrays of size 1 to 63
     * the numbers are in order and start at 0.
     * EX: list.size = 5   list = {0,1,2,3,4}
     */
    for (int i = 1; i < 64; i++) {
      Integer[] a = new Integer[i];
      for (int j = 0; j < i; j++) {
        a[j] = j;
      }
      RB_Tree.make(a);
      int bHeight = RB_Tree.height / 2 + 1;
      System.out.println("Tree Height: " + RB_Tree.height + "\tBlack Height: " + bHeight);
      System.out.println("Tree structure follows: (N = null, B = BLACK, R = RED)\n");
      RB_Tree.printTree(RB_Tree.root, 0, RB_Tree.height);
    }

    /*
     * To specifiy the numbers in the list one can run it like so:
     * 
     * RB_Tree.make(2,5,8,10,12,14,16,19,21,23,26,27);
     * int bHeight = RB_Tree.height / 2 + 1;
     * System.out.println("\t\t\t\t  Height: " + RB_Tree.height);
     * System.out.println("Tree structure follows:\n(N = null, B = BLACK, R = RED)\n");
     * RB_Tree.printTree(RB_Tree.root, 0, RB_Tree.height);
     */   
  }

  public RedBlackTree() {
    this.root = null;
  }

  public TNode getRoot() {
    return this.root;
  }

  public int getSize() {
    return this.height;
  }

  private void make(Integer[] list) {
    System.out.print("\n\nMaking RB Tree from sorted list:  [");
    for (int i = 0; i < list.length - 1; i++) {
      System.out.print(list[i] + ", ");
    }
    System.out.println(list[list.length - 1] + "]");

    this.height = (int) (Math.log10(list.length) / Math.log10(2));
    root = make(list, 0, list.length - 1, root, 0);
  }

  private TNode make(Integer[] list, int start, int end, TNode node, int h) {
    if (end < start) {
      return null;
    }

    int mid = start + (end - start) / 2;
    node = new TNode(list[mid]);
    node.setHeight(h);
    if (h != 0 && (h % 2 == this.height % 2)) {
      node.setColor("R");
    }

    node.setLeft(make(list, start, mid - 1, node, h + 1));
    node.setRight(make(list, mid + 1, end, node, h + 1));

    return node;
  }

  private void printTree(TNode node, int h, int maxHeight) {
    if (node == null) {
      if (h <= maxHeight) {
        System.out.print("N \n\t");
      }
      return;
    }

    printTree(node.getLeft(), h + 1, maxHeight);
    System.out.print(node.getValue() + node.getColor() + "\n");

    printTree(node.getRight(), h + 1, maxHeight);
    System.out.print("\t");
  }

  @Override
  public String toString() {
    return "RedBlackTree{" + "root=" + root + "}\n";
  }
}
